package com.leetcode.partition11;

import java.util.LinkedList;

/**
 * @author `RKC`
 * @date 2021/10/26 8:58
 */
public class LC1091二进制矩阵中的最短路径 {

    private static final int[][] dirs = {{1, 1}, {0, 1}, {1, 0}, {-1, 1}, {1, -1}, {-1, -1}, {-1, 0}, {0, -1}};

    public static int shortestPathBinaryMatrix(int[][] grid) {
        if (grid[0][0] == 1) return -1;
//        grid[0][0] = 2;
//        int answer = dfs(grid, 0, 0, 1);
//        return answer == Integer.MAX_VALUE ? -1 : answer;
        return bfs(grid);
    }

    public static void main(String[] args) {
//        int[][] grid = {{0, 1}, {1, 0}};
//        int[][] grid = {{0, 0, 0}, {1, 1, 0}, {1, 1, 0}};
        int[][] grid = {
                {0, 1, 1, 0, 1},
                {0, 1, 0, 1, 0},
                {0, 1, 0, 1, 0},
                {1, 0, 1, 1, 0},
                {1, 1, 1, 1, 0}
        };
        System.out.println(shortestPathBinaryMatrix(grid));
    }

    private static int bfs(int[][] grid) {
        LinkedList<int[]> queue = new LinkedList<>();
        grid[0][0] = 1;
        //<row, col, count>
        queue.add(new int[]{0, 0, 1});
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cur = queue.pollFirst();
                //最先到达终点的肯定是最短的
                if (cur[0] == grid.length - 1 && cur[1] == grid[0].length - 1) {
                    return cur[2];
                }
                for (int[] dir : dirs) {
                    int row = dir[0] + cur[0], col = dir[1] + cur[1];
                    //边界判断
                    if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] == 1) {
                        continue;
                    }
                    //加入队列并设置为已访问
                    queue.addLast(new int[]{row, col, cur[2] + 1});
                    grid[row][col] = 1;
                }
            }
        }
        return -1;
    }

    private static int dfs(int[][] grid, int i, int j, int count) {
        if (i == grid.length - 1 && j == grid[0].length - 1) return count;

        int res = Integer.MAX_VALUE;
        for (int[] dir : dirs) {
            int row = i + dir[0], col = j + dir[1];
            if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] == 1 || grid[row][col] == 2) {
                continue;
            }
            //标记为已经走过
            grid[row][col] = 2;
            res = Math.min(res, dfs(grid, row, col, count + 1));
            //回溯
            grid[row][col] = 0;
        }
        return res;
    }
}
